class Node{
    constructor(element){
        this.element = element;
        this.left = null;
        this.right = null;
    }
}
class Tree{
    constructor(){
        this.root = null;
        //后序遍历数组
        this.nextArr = [];
        //前序遍历数组
        this.preArr = [];
    }
    //插入
    insert(element){
        let node = new Node(element)//新node
        if(this.root === null){
            this.root = node;
        }else{
            this.insertNpde(node,this.root)//有头
        }
    }
    insertNpde(node,rootNode){
        if(node.element < rootNode.element){ //左边
            if(rootNode.left === null){
                rootNode.left = node
            }else{
                this.insertNpde(node,rootNode.left)
            }
        }else if(node.element > rootNode.element){//右边
            if(rootNode.right === null){
                rootNode.right = node
            }else{
                this.insertNpde(node,rootNode.right)
            }
        }
    }
    //后序遍历
    nextOrderrTraverse(){
        return  this.nextOrderrTraverseNode(this.root)
    }
    nextOrderrTraverseNode(node){
        if(node != null){
            this.nextOrderrTraverseNode(node.left)
            this.nextOrderrTraverseNode(node.right)
            this.nextArr.push(node.element)
        }
    }
    //前序遍历
    preOrderrTraverse(){
        return  this.preOrderrTraverseNode(this.root)
    }
    preOrderrTraverseNode(node){
        if(node != null){
            this.preArr.push(node.element)
            this.preOrderrTraverseNode(node.left)
            this.preOrderrTraverseNode(node.right)
        }
    }
    //最小值
    minNode(){
        return  this.getminNode(this.root)
    }
    getminNode(node){
        while(node.left != null){
            node = node.left
        }
        return node
    }
    //查找任意值
    search(element){
        return this.searchNode(element,this.root)
    } 
    searchNode(element,node){
        if(node === null){
            return false
        }

        if (element < node.element) {
            return this.searchNode(element, node.left)
        } else if (element > node.element) {
            return this.searchNode(element, node.right)
        } else {
            return true
        }
    }
    //冒泡
    MaoSort(arr){
        let {length} = arr

        for(let i = 1 ; i < length ; i++){
            for(let j = 0 ; j < length - i ; j++){
                if(arr[j] > arr[j+1]){
                    [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
                }
            }
        }
        console.log(arr,'冒泡')
    }
    //选择
    choseSort(arr){
        let {length} = arr;
        let min;//最小值的下标
        for(let i = 0 ; i < length ; i++){
            min = i
            for(let j = i +1 ;j < length ; j++){
                if(arr[j] < arr[min]){
                    min = j
                }
            }
            if(min != i){
                [arr[i],arr[min]] = [arr[min], arr[i]]
            }
        }
        
        console.log(arr,'选择')
    }
    //深度
    depath(){
        return this.maxDepath(this.root)
    }
    maxDepath(node){
        if(node === null){
            return 0
        }else{
            let leftDepath = this.maxDepath(node.left)
            let rightDepath = this.maxDepath(node.right)

            let childDepath = leftDepath > rightDepath ? leftDepath : rightDepath

            return childDepath +1
        }
    }
    //删除
    remove(element){
        return this.removeNode(element,this.root)
    }
    removeNode(element,rootNode){
        if(rootNode === null){
            return null
        }
        if(element < rootNode.element){
            rootNode.left = this.removeNode(element,rootNode.left)
            return rootNode
        }else if(element > rootNode.element){
            rootNode.right = this.removeNode(element,rootNode.right)
            return rootNode
        }else{
            //没有左右节点
            if(rootNode.left === null && rootNode.right === null){
                rootNode = null //删除本身
                return rootNode
            }
            //只有一个节点
            if(rootNode.left === null){
                rootNode = rootNode.right;
                return rootNode
            }else if(rootNode.right === null){
                rootNode = rootNode.left;
                return rootNode
            }
            
            //有两个节点
            let mNode = this.getminNode(rootNode.right);
            rootNode.element = mNode.element;
            rootNode.right = this.removeNode(mNode.element , rootNode.right)
            return rootNode
        }
    }
}
let t = new Tree();
t.insert(11)
t.insert(7)
t.insert(15)
t.insert(5)
t.insert(9)
t.insert(13)
t.insert(20)
t.insert(3)
t.insert(8)
t.insert(10)
t.insert(12)
t.insert(14)
t.insert(18)
t.insert(25)
t.nextOrderrTraverse();
t.preOrderrTraverse()
console.log(t.search(110))
console.log(t.minNode())
console.log(t.preArr)
t.MaoSort(t.preArr)

console.log(t.nextArr)
t.choseSort(t.nextArr)
console.log(t.depath(),'深度')
t.remove(3)
t.remove(5)
t.remove(15)
console.log(t)
